{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Range Sum of BST"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #binary-search-tree #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #二叉搜索树 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: rangeSumBST"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二叉搜索树的范围和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定二叉搜索树的根结点 <code>root</code>，返回值位于范围 <em><code>[low, high]</code></em> 之间的所有结点的值的和。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/11/05/bst1.jpg\" style=\"width: 400px; height: 222px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [10,5,15,3,7,null,18], low = 7, high = 15\n",
    "<strong>输出：</strong>32\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/11/05/bst2.jpg\" style=\"width: 400px; height: 335px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10\n",
    "<strong>输出：</strong>23\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点数目在范围 <code>[1, 2 * 10<sup>4</sup>]</code> 内</li>\n",
    "\t<li><code>1 <= Node.val <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 <= low <= high <= 10<sup>5</sup></code></li>\n",
    "\t<li>所有 <code>Node.val</code> <strong>互不相同</strong></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [range-sum-of-bst](https://leetcode.cn/problems/range-sum-of-bst/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [range-sum-of-bst](https://leetcode.cn/problems/range-sum-of-bst/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[10,5,15,3,7,null,18]\\n7\\n15', '[10,5,15,3,7,13,18,1,null,6]\\n6\\n10']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:\n",
    "        res = 0\n",
    "        \n",
    "        def visit(root):\n",
    "          nonlocal res\n",
    "          if not root:\n",
    "            return\n",
    "          if root.val < low:\n",
    "            visit(root.right)\n",
    "          elif root.val > high:\n",
    "            visit(root.left)\n",
    "          else:\n",
    "            res += root.val\n",
    "            visit(root.left)\n",
    "            visit(root.right)\n",
    "        \n",
    "        visit(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def rangeSumBST(self, root: TreeNode, L: int, R: int) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        res = 0\n",
    "        if L <= root.val <= R:\n",
    "            root.left = self.rangeSumBST(root.left, L, R)\n",
    "            root.right = self.rangeSumBST(root.right, L, R)\n",
    "            res += root.val\n",
    "        elif root.val < L:\n",
    "            root.right = self.rangeSumBST(root.right, L, R)\n",
    "            root.left = 0\n",
    "        else:\n",
    "            root.left = self.rangeSumBST(root.left, L, R)\n",
    "            root.right = 0\n",
    "\n",
    "        return res+root.left+root.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from queue import LifoQueue\n",
    "class Solution:\n",
    "    def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:\n",
    "        result = 0\n",
    "        heap = LifoQueue()\n",
    "        heap.put(root)\n",
    "        while heap.qsize() != 0:\n",
    "            _root = heap.get()\n",
    "            if _root is None:\n",
    "                continue\n",
    "            if _root.left is None and _root.right is None:\n",
    "                if low <= _root.val <= high:\n",
    "                    result += _root.val\n",
    "                continue\n",
    "            _right = _root.right\n",
    "            _left = _root.left\n",
    "            _root.left = None\n",
    "            _root.right = None\n",
    "            if _root.val < high and _right is not None:\n",
    "                heap.put(_right)\n",
    "            if low <= _root.val <= high:\n",
    "                heap.put(_root)\n",
    "                _root.left = None\n",
    "                _root.right = None\n",
    "            if _root.val > low and _left is not None:\n",
    "                heap.put(_left)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def rangeSumBST(self, root: TreeNode, L: int, R: int) -> int:\n",
    "        def recursion(node):\n",
    "            if node: \n",
    "                if node.val >= L: recursion(node.left)        \n",
    "                if L <= node.val <= R: self.res += node.val                \n",
    "                if node.val <= R: recursion(node.right)\n",
    "        \n",
    "        self.res = 0\n",
    "        recursion(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def rangeSumBST(self, root: TreeNode, L: int, R: int) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        if root.val < L:\n",
    "            return self.rangeSumBST(root.right, L, R)\n",
    "        if root.val > R:\n",
    "            return self.rangeSumBST(root.left, L, R)\n",
    "        res = root.val\n",
    "        res += self.rangeSumBST(root.left, L, R)\n",
    "        res += self.rangeSumBST(root.right, L, R)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def rangeSumBST(self, root: TreeNode, L: int, R: int) -> int:\n",
    "        ret = 0\n",
    "        if root:\n",
    "            if L <= root.val <= R:\n",
    "                ret = root.val\n",
    "            if root.val <= R:\n",
    "                ret += self.rangeSumBST(root.right, L, R)\n",
    "            if root.val >= L:\n",
    "                ret += self.rangeSumBST(root.left, L, R)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def rangeSumBST(self, root: TreeNode, L: int, R: int) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        cur, stack, res = root, [], []\n",
    "        while cur or stack:\n",
    "            while cur:\n",
    "                stack.append(cur)\n",
    "                cur = cur.left\n",
    "            node = stack.pop()\n",
    "            if node.val >= L and node.val <= R:\n",
    "                res.append(node.val)\n",
    "            cur = node.right\n",
    "        return sum(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:\n",
    "        stack = []\n",
    "        current = root\n",
    "        sum = 0\n",
    "        while current or len(stack)>0:\n",
    "            while current.left:\n",
    "                stack.append(current)\n",
    "                current = current.left\n",
    "                stack[-1].left = None\n",
    "            if current.val > high:\n",
    "                break\n",
    "            if current.val >= low:\n",
    "                sum += current.val\n",
    "            if current.right:\n",
    "                current = current.right\n",
    "            elif len(stack)>0:\n",
    "                current = stack.pop()\n",
    "            else:\n",
    "                break\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:\n",
    "        self.sum=0\n",
    "        self.inorder(root,low,high)\n",
    "        return self.sum\n",
    "    def inorder(self,root,low,high):\n",
    "        if not root:\n",
    "            return \n",
    "        if root:\n",
    "            self.inorder(root.left,low,high)\n",
    "            if  root.val<low:\n",
    "                root.left=None\n",
    "            elif root.val>high:\n",
    "                root.right=None\n",
    "            else: \n",
    "                self.sum+=root.val\n",
    "            self.inorder(root.right,low,high)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def rangeSumBST(self, root, low: int, high: int) -> int:\r\n",
    "        res = 0\r\n",
    "        cur = root\r\n",
    "        while cur:\r\n",
    "            if cur.val < low:\r\n",
    "                cur.left = None\r\n",
    "            elif cur.val > high:\r\n",
    "                cur.right = None\r\n",
    "            if cur.left is None:\r\n",
    "                if cur.val >= low and cur.val <= high:\r\n",
    "                    res += cur.val\r\n",
    "                cur = cur.right\r\n",
    "            else:\r\n",
    "                max_right = cur.left\r\n",
    "                while max_right.right is not None and max_right.right != cur:\r\n",
    "                    max_right = max_right.right\r\n",
    "                if max_right.right is None:\r\n",
    "                    max_right.right = cur\r\n",
    "                    cur = cur.left\r\n",
    "                else:\r\n",
    "                    max_right.right = None\r\n",
    "                    if cur.val >= low and cur.val <= high:\r\n",
    "                        res += cur.val\r\n",
    "                    cur = cur.right\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def rangeSumBST(self, root: TreeNode, L: int, R: int) -> int:\n",
    "        from queue import Queue\n",
    "        node_queue = Queue()\n",
    "        node_queue.put(root)\n",
    "        cnt = 0\n",
    "        while not node_queue.empty():\n",
    "            node = node_queue.get()\n",
    "            if node is not None:\n",
    "                if node.val is not None and L <= node.val <= R:\n",
    "                    cnt += node.val\n",
    "                if node.left is not None:\n",
    "                    node_queue.put(node.left)\n",
    "                if node.right is not None:\n",
    "                    node_queue.put(node.right)\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:\n",
    "        if not root: return 0\n",
    "        if  root.val > high:\n",
    "            return self.rangeSumBST(root.left,low,high)\n",
    "        if root.val < low:\n",
    "            return self.rangeSumBST(root.right,low,high)\n",
    "        return root.val + self.rangeSumBST(root.left,low,high) + self.rangeSumBST(root.right,low,high)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:\n",
    "        x=[root]\n",
    "        s=0\n",
    "        while x:\n",
    "            t=x.pop()\n",
    "            if not t:\n",
    "                continue\n",
    "            if t.val>high:\n",
    "                x.append(t.left)\n",
    "            elif t.val<low:\n",
    "                x.append(t.right)\n",
    "            else:\n",
    "                s+=t.val\n",
    "                x.append(t.left)\n",
    "                x.append(t.right)\n",
    "        return s\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:\n",
    "        if root is None:\n",
    "            return 0\n",
    "        leftSum = self.rangeSumBST(root.left,low,high)\n",
    "        rightSum = self.rangeSumBST(root.right,low,high)\n",
    "        result =leftSum+rightSum\n",
    "        if root.val>=low and root.val<=high:\n",
    "            result += root.val\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:\n",
    "        self.cur = 0\n",
    "        def dfs(node):\n",
    "            if node.left:\n",
    "                dfs(node.left)\n",
    "            if node.val > high:\n",
    "                return\n",
    "            if node.val >= low:\n",
    "                self.cur += node.val\n",
    "            if node.right:\n",
    "                dfs(node.right)\n",
    "        dfs(root)\n",
    "        return self.cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:\n",
    "        # 中序遍历二叉搜索树等于遍历有序数组\n",
    "        if not root:\n",
    "            return 0\n",
    "        if root.val > high:\n",
    "            return self.rangeSumBST(root.left,low,high)\n",
    "        elif root.val < low: #搜索树，左子树全部节点值小于又子树,全部抛弃\n",
    "            return self.rangeSumBST(root.right,low,high)\n",
    "        else:\n",
    "            return self.rangeSumBST(root.left,low,high) + root.val + self.rangeSumBST(root.right,low,high)\n",
    "            \n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:\n",
    "        if root is None:\n",
    "            return 0\n",
    "        if root.val < low:\n",
    "            return self.rangeSumBST(root.right , low , high)\n",
    "        if root.val >high:\n",
    "            return self.rangeSumBST(root.left , low , high)\n",
    "        return root.val + self.rangeSumBST(root.left , low , high) + self.rangeSumBST(root.right , low , high)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:\n",
    "        cur=root\n",
    "        nums=[]\n",
    "        def dfs(cur):\n",
    "            if low<=cur.val<=high:\n",
    "                nums.append(cur.val)\n",
    "            if cur.left:\n",
    "                dfs(cur.left)\n",
    "            if cur.right:\n",
    "                dfs(cur.right)\n",
    "        dfs(cur)\n",
    "        return sum(nums) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:\n",
    "        stack = [root]\n",
    "        visited =set()\n",
    "        ans = 0\n",
    "        while len(stack) != 0:\n",
    "            tail = stack[-1]\n",
    "            if tail.left is not None and tail.left not in visited:\n",
    "                stack.append(tail.left)\n",
    "            else:\n",
    "                stack.pop()\n",
    "                visited.add(tail)\n",
    "                if tail.val > high:\n",
    "                    return ans\n",
    "                if tail.val >= low:\n",
    "                    ans+=tail.val \n",
    "                if tail.right is not None:\n",
    "                    stack.append(tail.right)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:\n",
    "        if root is None:\n",
    "            return 0\n",
    "\n",
    "        if root.val < low:\n",
    "            return self.rangeSumBST(root.right, low, high)\n",
    "        elif root.val > high:\n",
    "            return self.rangeSumBST(root.left, low, high)\n",
    "        else:\n",
    "            return root.val \\\n",
    "                    + self.rangeSumBST(root.left, low, high) \\\n",
    "                    + self.rangeSumBST(root.right, low, high)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        if root.val > high:\n",
    "            return self.rangeSumBST(root.left, low, high)\n",
    "        if root.val < low:\n",
    "            return self.rangeSumBST(root.right, low, high)\n",
    "        return root.val + self.rangeSumBST(root.left, low, high) + self.rangeSumBST(root.right, low, high)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
